
 
  struct Node {
      int val;
      struct Node *next;
      struct Node *random;
  };
 

struct Node* BuyNode(int x)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->val = x;
    newNode->random = NULL;
    return newNode;
}
struct Node* copyRandomList(struct Node* head)
{
    if (head == NULL)
    {
        return NULL;
    }
    struct Node* copy, * cur, * next, * retHead, * retTail;
    retHead = retTail = BuyNode(0);
    cur = head;
    while (cur)
    {
        next = cur->next;
        cur->next = copy = BuyNode(cur->val);
        copy->next = next;
        cur = next;
    }
    cur = head;
    while (cur)
    {
        copy = cur->next;
        if (cur->random != NULL)
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    cur = head;
    while (cur)
    {
        copy = cur->next;
        retTail->next = copy;
        retTail = retTail->next;
        cur->next = copy->next;
        cur = cur->next;
    }
    return retHead->next;
}